package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC738 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int monotoneIncreasingDigits(int N) {
            String num = String.valueOf(N);
            char[] res = new char[num.length()];
            boolean monoFlag = true;

            for (int i = 0; i < num.length(); i++) {
                if (!monoFlag) {
                    res[i] = '9';
                    continue;
                }

                if (i == num.length() - 1) {
                    res[i] = num.charAt(i);
                    break;
                }

                if (num.charAt(i) <= num.charAt(i + 1)) {
                    res[i] = num.charAt(i);
                    continue;
                } else {
                    monoFlag = false;
                    int j = i;
                    while (j - 1 >= 0 && num.charAt(j) == num.charAt(j - 1)) --j;
                    res[j] = (char) (num.charAt(j) - 1);
                    while (++j <= i) res[j] = '9';
                }
            }

            return Integer.parseInt(new String(res));
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.monotoneIncreasingDigits(777616726));
    }

    public static void main(String[] args) throws Exception {
        LC738 an = new LC738();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
